package com.azdebugit.java8.suanfa;

import java.util.*;

class SolutionCc {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int pre = Integer.MIN_VALUE;
        List<List<Integer>> res = new ArrayList<>();
        for(int i=0;i<n;i++){
            if(nums[i]!=pre){
                int[] flags = new int[n];
                List<Integer> one = new ArrayList<>();
                flags[i]=1;
                one.add(nums[i]);
                get(nums,res,one,flags);
                pre = nums[i];
            }
        }
        return res;
    }

    //dfs(int[] candidates, int target,int max, Deque<Integer> numS,List<List<Integer>> resList){
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> sequence = new ArrayList<>();
//    List<Deque<Integer> > freq = new ArrayList<>();
    List<Integer[]> freq = new ArrayList<>();
    Deque<Integer> numS = new ArrayDeque<>();
    public void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        if (pos == freq.size() || rest < freq.get(pos)[0]) {
            return;
        }
        // 这一步递归 就是访问数组的最后一个位置
        dfs(pos + 1, rest);
        // 然后从当前pos，一直到最后一个pos位置
        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for (int i = 1; i <= most; ++i) {
            sequence.add(freq.get(pos)[0]);
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        // 回溯
        for (int i = 1; i <= most; ++i) {
            sequence.remove(sequence.size() - 1);
        }
    }




    public void get(int[] nums,List<List<Integer>> res,List<Integer> re,int[] flags){
        if (re.size() == nums.length){
            res.add(re);
            return;
        }
        int n = nums.length;
        int pre = Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
        // pre 就是上一个数
            if(nums[i]!=pre && flags[i]==0){
                List<Integer> one = new ArrayList<>(re);
                one.add(nums[i]);
                flags[i]=1;
                get(nums,res,one,flags);
                pre = nums[i];
                flags[i]=0;
            }
            
        }
    }
}


